<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        //在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
        let array = [
            [1, 2, 3, 4],
            [2, 3, 4, 5],
            [3, 4, 5, 6],
            [4, 5, 6, 7]
        ]

        /**
         * 解法1：
         * 将数组的分为行和列,
         * 从最后一列靠开始比较，如果target 小于最后一行第一个则去寻找倒数第二行(j--),如果target大于某一行的第一个则在此行寻找
         * 时间复杂度:O(n+m)
         */
        // function find(target, array) {
        //     let row = array.length;
        //     let col = array[0].length;
        //     if (row === 0 && col === 0) return false
        //     if (target < array[0][0] || target > array[row - 1][col - 1]) return false;
        //     let i = 0,
        //         j = col - 1;
        //     while (i < row && j >= 0) {
        //         if (target > array[i][j]) {
        //             i++;
        //         } else if (target < array[i][j]) {
        //             j--;
        //         } else {
        //             return true;
        //         }
        //     }
        // }



        /**
         * 解法2:将二维数组合并为一维数组，然后使用indexOf,includes,arr.find()查询
         * 时间复杂度:O(n)
         */
        function find(target, array) {
            let arr = [];
            for (let i = 0; i < array.length; i++) {
                arr = arr.concat(array[i])
            }
            // return arr.indexOf(target) >= 0; 
            // return arr.includes(target); 
            return arr.find(item => {
                return target === item
            }) ? true : false
        }
        console.log(find(6, array))
    </script>
</body>

</html>